﻿// 401 遍历完全二叉树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

using namespace std;
/*
http://oj.daimayuan.top/course/7/problem/430

给你一棵 n个节点的完全二叉树，节点的编号为 1到 n，二叉树的根为 1号节点。
 编号为 i (1≤i≤n)的节点的左儿子如果存在的话，编号为 i+i；
 编号为 i (1≤i≤n)的节点的右儿子如果存在的话，编号为 i+i+1。

现在请你求出这棵完全二叉树的先序、中序和后序遍历的结果。

输入格式
一行一个整数 n。

输出格式
输出三行，每行 n个数代表一种遍历的结果。

第一行为先序遍历的结果，第二行为中序遍历的结果，第三行为后序遍历的结果。

样例输入
7
样例输出
1 2 4 5 3 6 7
4 2 5 1 6 3 7
4 5 2 6 7 3 1
数据规模
对于所有数据，保证 1≤n≤1024。
*/

int n;

void preOrder(int x) {
	if (x > n) return;
	cout << x << " ";
	preOrder(2 * x);
	preOrder(2*x+1);
}

void inOrder(int x) {
	if (x > n)return;
	inOrder(2 * x);
	cout << x << " ";
	inOrder(2 * x + 1);
}

void postOrder(int x) {
	if (x > n)return;
	postOrder(2 * x);
	postOrder(2 * x + 1);
	cout << x << " ";
}

int main()
{
	cin >> n;
	preOrder(1);
	cout << endl;
	inOrder(1);
	cout << endl;
	postOrder(1);
	cout << endl;
}

 